package BinarySearch;

/*
寻找比目标字母大的最小字母
给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters里至少有两个不同的字符。
返回letters中大于 target 的最小的字符。如果不存在这样的字符，则返回letters 的第一个字符。

示例 1：
输入: letters = ["c", "f", "j"]，target = "a"
输出: "c"
解释：letters 中字典上比 'a' 大的最小字符是 'c'。
示例 2:
输入: letters = ["c","f","j"], target = "c"
输出: "f"
解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。
示例 3:
输入: letters = ["x","x","y","y"], target = "z"
输出: "x"
解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/binary-search/xeiuui/
 */

public class _63寻找比目标字母大的最小字母 {
    public static void main(String[] args) {

    }

    //二分查找 第二模板
    public char nextGreatestLetter(char[] letters, char target) {
        if(letters[letters.length-1] <= target){
            return letters[0];
        }
        int left = 0, right = letters.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (letters[mid] > target) {
                right = mid;
            }else{
                left = mid + 1;
            }
        }
//        优化  在代码一开始加入数组最后一个字符与目标字符的判断，如果小直接返回
//        反之则必存在一个字符大于目标字符，故可以去掉对最后一个元素的判断
//        if (letters[left] > target) {
//            return letters[left];
//        }
//        return letters[0];
        return letters[left];
    }
}
